#include "linearList.h"

void linkList::merge(linkList& b){
	lastNode->next = b.firstNode -> next;
	lastNode = b.lastNode ;
	listSize += b.listSize ;
	b.listSize = 0;
	b.firstNode -> next = NULL;
	b.lastNode = firstNode;
}
void merge(linkList&a, linkList&b){
	a.merge(b);
	a.ascendingOrder();
	a.reverse();
}
//顺序表打印
void sequenceList::print()
{
    std::cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        std::cout << myList[i] << ",";
    }

    std::cout << myList[curNumberOfItem-1] <<std::endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    std::cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
           std:: cout << curNode->next->data << std::endl;
        else
        {
           std:: cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

sequenceList::sequenceList(const int& a, const int& b, float c[]){
        maxCapcity = a;
        curNumberOfItem = b > a ? a : b;
        myList = new float[maxCapcity];
        for (int i = 0; i < curNumberOfItem; i++) {
            myList[i] = c[i];
        }
}
sequenceList::~sequenceList(){
	 delete[] myList;
	};
bool sequenceList::addItem(const float& item){
	        if (curNumberOfItem >= maxCapcity) {
            return false;
        }
        myList[curNumberOfItem] = item;
        curNumberOfItem++;
        return true;
} 
bool sequenceList::insertItem(const int &pos,const float &item){
	 if (pos < 0 || pos > curNumberOfItem || curNumberOfItem >= maxCapcity) {
            return false;
        }
        for (int i = curNumberOfItem; i > pos; i--) {
            myList[i] = myList[i - 1];
        }
        myList[pos] = item;
        curNumberOfItem++;
        return true;
} 
int sequenceList::deleteItem(const float&item){
	        int pos = -1; //要删除元素的位置
    for(int i = 0; i < curNumberOfItem; i++)
    {
        if(myList[i] == item) //找到要删除的元素
        {
            pos = i;
            break;
        }
    }
    if(pos == -1) //未找到
        return -1;
    else //找到
    {
        for(int i = pos; i < curNumberOfItem-1; i++)
            myList[i] = myList[i+1]; //移动元素位置
        curNumberOfItem--; //当前元素数量减1
        return pos;
    }
}
bool sequenceList::locate(const int& pos, float& item) {
	        if (pos < 0 || pos >= curNumberOfItem) {
            return false;
        }
        item = myList[pos];
        return true;
}
int sequenceList::locate(const float&item) {
	        for (int i = 0; i < curNumberOfItem; i++) {
            if (myList[i] == item) {
                return i;
            }
        }
        return -1;
}
void sequenceList::reverse() {
	        for (int i = 0; i < curNumberOfItem / 2; i++) {
            float temp = myList[i];
            myList[i] = myList[curNumberOfItem - i - 1];
            myList[curNumberOfItem - i - 1] = temp;
        }
}
listNode::listNode(float nodeData,listNode* succ){
	data = nodeData;
    next = succ;
} 
listNode::~listNode(){
    //do nothing
}
linkList::linkList(){
    firstNode = new listNode;
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;
}
linkList::linkList(const int& size, float arr[]){
    firstNode = new listNode;
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;
    for(int i=0; i<size; i++){
        tailInsertItem(arr[i]);
    }
}
linkList::~linkList(){
    listNode* temp;
    while(firstNode != NULL){
        temp = firstNode;
        firstNode = firstNode->next;
        delete temp;
    }
}
bool linkList::headInsertItem(const float& item){
    listNode* newNode = new listNode(item, firstNode->next);
    if(newNode == NULL){
        return false;
    }
    firstNode->next = newNode;
    if(lastNode == firstNode){
        lastNode = newNode;
    }
    listSize++;
    return true;
}
bool linkList::tailInsertItem(const float& item){
    listNode* newNode = new listNode(item);
    if(newNode == NULL){
        return false;
    }
    lastNode->next = newNode;
    lastNode = newNode;
    listSize++;
    return true;
}
int linkList::insertItem(const int& position, const float& item){
    if(position < 0 || position > listSize){
        return -1;
    }
    if(position == 0){
        headInsertItem(item);
        return 0;
    }
    listNode* temp = firstNode;
    for(int i=0; i<=position-1; i++){
        temp = temp->next;
    }
    listNode* newNode = new listNode(item, temp->next);
    if(newNode == NULL){
        return -1;
    }
    temp->next = newNode;
    if(lastNode == temp){
        lastNode = newNode;
    }
    listSize++;
    return position;
}
int linkList::deleteItem(const float& item){
    listNode* temp = firstNode;
    int position = 0;
    while(temp->next != NULL && temp->next->data != item){
        temp = temp->next;
        position++;
    }
    if(temp->next == NULL){
        return -1;
    }
    listNode* delNode = temp->next;
    temp->next = delNode->next;
    if(lastNode == delNode){
        lastNode = temp;
    }
    delete delNode;
    listSize--;
    return position;
}
bool linkList::locate(const int& position, float& item){
    if(position < 0 || position >= listSize){
        return false;
    }
    listNode* temp = firstNode->next;
    for(int i=0; i<position; i++){
        temp = temp->next;
    }
    item = temp->data;
    return true;
}
int linkList::locate(const float& item){
    listNode* temp = firstNode->next;
    int position = 0;
    while(temp != NULL && temp->data != item){
        temp = temp->next;
        position++;
    }
    if(temp == NULL){
        return -1;
    }
    return position;
}
void linkList::ascendingOrder()
{
    listNode* p = firstNode->next;
    listNode* pre = firstNode;
    while (p != NULL) {
        listNode* q = p->next;
        listNode* qpre = p;
        while (q != NULL) {
            if (q->data < p->data) {
                qpre->next = q->next;
                if (q == lastNode) {
                    lastNode = qpre;
                }
                q->next = p;
                pre->next = q;
                listNode* temp = p;
                p = q;
                q = temp;
            }
            qpre = q;
            q = q->next;
        }
        pre = p;
        p = p->next;
    }
}
void linkList::reverse()
{
    if (listSize <= 1)
    {
        return;
    }
    listNode* prevNode = nullptr;
    curNode = firstNode->next;
    lastNode = curNode;
    while (curNode != nullptr)
    {
        listNode* nextNode = curNode->next;
        curNode->next = prevNode;
        prevNode = curNode;
        curNode = nextNode;
    }
    firstNode->next = prevNode;
}